#ifndef CS240_LINKED_LIST_H
#define CS240_LINKED_LIST_H

#include <string>
using namespace std;


//! LLNode implements a doubly-linked list node
template <class T>
class LLNode{
	template <class TT> friend class LinkedList;  //!< LinkedList can access private members of LLNode
	public:

		//!  Constructor
		LLNode(const T & v, LLNode * p, LLNode * n) :
		  value(&v), prev(p), next(n)
		{
		}

		//! Copy Constructor
		LLNode(const LLNode & other) :
		   value(other.value),prev(other.prev),next(other.next)
		{
		}
		~LLNode(){
			delete(value);
		}

		//!  Read-only public methods for use by clients of the LinkedList class
		const T & GetValue() const
		{
		  return *value;
		}


		LLNode * GetPrevious()const
		{
		  return prev;
		}


		LLNode * GetNext()const
		{
		  return next;
		}

		//! Assignment operator
		LLNode & operator=(const LLNode & other)
		{
			if(this!=&other)
			{
				value=other.value;
				prev=other.prev;
				next=other.next;
			}
			return *this;
		}

	private:
		const T * value;        //!< value stored in the node
		LLNode<T> * prev;            //!< pointer to previous node in the list
		LLNode<T> * next;            //!< pointer to next node in the list
};


//! LinkedList implements a doubly-linked list
template <class T>
class LinkedList
{
	public:

		//!  No-arg constructor.  Initializes an empty linked list
		LinkedList():first(NULL),last(NULL),size(0){

		}


		//!  Copy constructor.  Makes a complete copy of its argument
		LinkedList(const LinkedList & other):first(NULL),last(NULL),size(0){
			copy(other);
		}


		//!  Destructor
		~LinkedList(){
 			Clear();
		}


		//! Assignment operator.  Makes a complete copy of its argument
		//! @return A reference to oneself
		LinkedList& operator =(const LinkedList & other){
			if(&other == this)
					return *this;
			copy(other);
			return *this;
		}


		//!  @return true if the list is empty, or false if the list is not empty
		bool IsEmpty() const{
			if (size==0)
				return true;
			else
				return false;
		}


		//!  Removes all values from the list
		void Clear(){
			LLNode<T> * start = GetFirst();
			while(start!=NULL){
				LLNode<T> * temp = start;
				start = start->next;
				Remove(temp);
			}
			last = NULL;
			first = NULL;
			size = 0;
		}


		//!  @return the number of values in the list
		int GetSize() const{
			return size;
		}



		//!  @return a pointer to the first node in the list, or NULL if the list is empty
		LLNode<T> * GetFirst()const{
			return first;
		}



		//!  @returns a pointer to the last node in the list, or NULL if the list is empty
		LLNode<T> * GetLast()const{
			return last;
		}


		//!  Inserts value v into the list after node n
		//!
		//!  @param v The new value being inserted
		//!  @param n A node that is already in the list after which the new node should
		//!      be inserted.
		//!      If n is NULL, the new node should be inserted at the beginning of the list.
		//!
		//!  @return a pointer to the newly inserted node
		LLNode<T> * Insert(const T & v, LLNode<T> * n = NULL){
			LLNode<T> * current = first;
			if(n == NULL){
				LLNode<T> * newNode;
				if(first!=NULL){
					newNode = new LLNode<T>(v,NULL,NULL);
					first->prev = newNode;
					newNode->next = first;
				}else{
					newNode = new LLNode<T>(v,NULL,NULL);
					last = newNode;
				}
				first = newNode;
				size++;
				return newNode;
			}
			while(current != NULL){
				if(current == n){
					LLNode<T> * newNode = new LLNode<T>(v,current,current->GetNext());
					if(current->next != NULL)
						current->next->prev = newNode;
					else
						last = newNode;
					current->next = newNode;
					size++;
					return newNode;
				}
				current = current->next;
			}
			return NULL;
		}


		//! Searches for the first occurrence of value v that appears in the list
		//!   after node n
		//!
		//!  @param v The value being searched for
		//!  @param n The node in the list after which the search should begin.
		//!      If n is NULL, the list should be searched from the beginning.
		//!
		//!  @return a pointer to the node containing v, or NULL if v is not found
		LLNode<T> * Find(const std::string & v, LLNode<T> * n) const{
			LLNode<T> * current = first;
			bool beginSearch = false;
			if(n==NULL)
				beginSearch = true;
			while(current != NULL){
				//Only begin search after the given node
				if(current == n){
					beginSearch = true;
					current = current->next;
					continue;
				}
				if(beginSearch == true && current->value==v){
					return current;
				}
				current = current->next;
			}
			return NULL;
		}

		//!  Removes node n from the list
		//!
		//!  @param n The node being removed from the list
		void Remove(LLNode<T> * n){
			LLNode<T> * current = first;
			while(current != NULL){
				if(current == n){
					if(current->prev!=NULL)
						current->prev->next = current->next;
					else
						first = current->next;
					if(current->next!=NULL)
						current->next->prev = current->prev;
					else
						last = current->prev;
					size--;
					delete(current);

					current = NULL;
					break;

				}
				current = current->next;
			}
			return;
		}



	private:
		LLNode<T> * first;
		LLNode<T> * last;
		int size;
		void copy(const LinkedList& other){
			Clear();
			LLNode<T> * pointer = other.GetLast();
			while( pointer!=NULL){
				Insert(*pointer->value,NULL);
				pointer = pointer->prev;
			}
		}
};


#endif
